package com.leetcode.动态规划;

/**
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
 * 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 * <p>
 * 链接：https://leetcode-cn.com/problems/house-robber
 */
public class 打家劫舍 {
    /**
     * 方案一：递归调用
     * 复杂度: T(n-1) + T(n-2) + O(1)
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        return this.rob(nums, 0);
    }
    /**
     * 从第begin号房子开始偷
     */
    public int rob(int[] nums, int begin) {
        // 边际条件
        if (begin == nums.length - 1) return nums[begin];
        if (begin == nums.length - 2) return Math.max(nums[begin], nums[begin + 1]);

        // 两种选择
        // 1. 偷第 begin 家
        int robCur = nums[begin] + this.rob(nums, begin + 2);
        // 2. 偷第 begin + 1 家
        int robNext = this.rob(nums, begin + 1);
        return Math.max(robCur, robNext);
    }

    /**
     * 方案二：动态规划
     */
    public int rob2(int[] nums) {
        return 0;
    }


    public static void main(String[] args) {
        int[] room= {1};

        System.out.println(new 打家劫舍().rob(room));
    }
}
